package leetcode101.greedy_strategy;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code5
 * @Description 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
 * 由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
 *
 * 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。
 * 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart≤ x ≤ xend，则该气球会被引爆。
 * 可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
 *
 * 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
 *
 * 示例 1：
 *
 * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
 * 输出：2
 * 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
 * 示例 2：
 *
 * 输入：points = [[1,2],[3,4],[5,6],[7,8]]
 * 输出：4
 * 示例 3：
 *
 * 输入：points = [[1,2],[2,3],[3,4],[4,5]]
 * 输出：2
 * 示例 4：
 *
 * 输入：points = [[1,2]]
 * 输出：1
 * 示例 5：
 *
 * 输入：points = [[2,3],[2,3]]
 * 输出：1
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-22 15:36
 */
public class Code5 {

    public static void main(String[] args) {
//        int[][] arr = {{10,16},{2,8},{1,6},{7,12}};
        int[][] arr = {{1, 5},{2,6},{3,7},{4,11},{8,15},{9,13},{10,12},{14,17},{16,18}};
        System.out.println(findMinArrowShots(arr));
    }

    public static int findMinArrowShots(int[][] points) {
//        quickSort(points, 0, points.length - 1);
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        ArrayList<int[]> list = new ArrayList<>();
        for (int i = 0; i < points.length; i++) {
            list.add(i, points[i]);
        }

        int counter = 0; // counter记录箭的个数
//        int pointer = 0; // pointer为arrayList的指针
        while (list.size() != 0) {
            int last = list.get(0)[1];
            list.removeIf(ints -> last >= ints[0]);
            counter++;
        }
        return counter;
    }

//    public static void quickSort(int[][] arr, int low, int high) {
//        if (low < high) {
//            int pivot = partition(arr, low, high);
//            quickSort(arr, low, pivot - 1);
//            quickSort(arr, pivot + 1, high);
//        }
//    }
//
//    public static int partition(int[][] arr, int low, int high) {
//        int[] temp = arr[low];
//        while (low < high) {
//            while (low < high && arr[high][1] >= temp[1]) high--;
//            arr[low] = arr[high];
//            arr[high] = temp;
//
//            while (low < high && arr[low][1] <= temp[1]) low++;
//            arr[high] = arr[low];
//            arr[low] = temp;
//        }
//        return low;
//    }

}
